package problem42;

//42.接雨水
//https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked

//单调栈

import java.util.Stack;

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int n = height.length;
        int sum = 0;
        stack.push(0);
        for(int i = 1; i<n; i++) {
            if(height[i] < height[stack.peek()]) {
                stack.push(i);
            }else {
                while(!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                    int mid = stack.pop();
                    if(!stack.isEmpty()) {
                        int w = i-stack.peek()-1;
                        int h = Math.min(height[stack.peek()], height[i])-height[mid];
                        sum += w*h;
                    }
                }
                stack.push(i);
            }
        }
        return sum;
    }
}